#include<bits/stdc++.h>
using namespace std;

vector<int> zfun(string s) {
    int n = s.size();
    vector<int> f(n);
    f[0] = n;
    for(int i = 1, l, r = -1; i < n; i++) {
        if(i <= r) f[i] = min(r - i + 1, f[i - l]);
        while(s[i + f[i]] == s[f[i]]) f[i]++;
        if(i + f[i] - 1 >= r) r = i + f[i] - 1, l = i;
    }
    return f;
}
vector<int> kmp (string s) {
	int n = s.size();
	vector<int> f(n + 1);
	for(int i = 1, j = 0; i < n; i++) {
		while(j && s[i] != s[j]) j = f[j];
		j += s[i] == s[j];
		f[i + 1] = j;
	}
	return f;
}
vector<int> manacher (string &s) {
	string t = "*#";
	for(auto c : s) {
		t.push_back(c);
		t.push_back('#');
	}
	int n = t.size();
	vector<int> p(n);
	
	p[1] = 1;
	for(int i = 2, l, r = 1; i < n; i++) {
		if(i < r) p[i] = min(p[l + r - i], r - i + 1);
		while(t[i - p[i]] == t[i + p[i]]) p[i]++;
		if(i + p[i] - 1 > r) {
			r = i + p[i] - 1;
			l = i - p[i] + 1;
		}
	}
	return p;
}

// 字符串双hash， 需要考虑N，且需要初始化
#define a2 array<ll, 2>
const int N = 5e5 + 10;
mt19937 rd(time(0));
int gen(int l, int r) {
    return rd() % (r - l + 1) + l;
}
ll mod[2] = {998244353, (int)1e9 + 7}, bas[2] = {gen(100, 10000), gen(100, 10000)}, p[2][N];
void init_hash() {
    for (int t = 0; t < 2; t++) {
        p[t][0] = 1;
        for (int i = 1; i < N; i++) {
            p[t][i] = p[t][i - 1] * bas[t] % mod[t];
        }
    }
} 
struct H {
    int len;
    a2 h;

    H operator+(const H& t) const {
        return {len + t.len, {(h[0] * p[0][t.len] + t.h[0]) % mod[0], (h[1] * p[1][t.len] % mod[1] + t.h[1]) % mod[1]}};
    }
    bool operator<(const H& t) const {
        return h < t.h;
    }
    bool operator==(const H& t) const {
        return len == t.len && h == t.h;
    }
};
struct Hash_H {
    size_t operator() (const H& t) const {
        return hash<int>()(t.len) ^ (hash<ll>()(t.h[0]) << 3) ^ (hash<ll>()(t.h[1]) << 5);
    }
};
struct Hash {
    vector<a2> h;
    template<class T> // string or vector
    Hash(T s) {
        int n = s.size();
        h.assign(n, {});
        h[0][0] = h[0][1] = s[0];
        for (int i = 1; i < n; i++) {
            for (int t = 0; t < 2; t++) {
                h[i][t] = (h[i - 1][t] * bas[t] + s[i]) % mod[t];
            }
        }
    }
    H get(int l, int r) {
        if (l > r) {
            return {0, {0, 0}};
        }
        a2 res;
        for (int t = 0; t < 2; t++) {
            ll val = h[r][t] - (l ? h[l - 1][t] : 0) * p[t][r - l + 1];
            res[t] = (val % mod[t] + mod[t]) % mod[t];
        }
        return {r - l + 1, res};
    }
};

struct SA {
	int n;
	vector<int> rk, sa, st[20];
	
	SA(string s) {
		n = s.size();
		rk.resize(n), sa.resize(n);
		for(int i = 0; i < 20; i++) st[i].resize(n);
		
		iota(sa.begin(), sa.end(), 0);
		sort(sa.begin(), sa.end(), [&](int x, int y) {
			return s[x] < s[y];
		});
		rk[sa[0]] = 0;
		for(int i = 1; i < n; i++) rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
		
		vector<int> cnt(n), tmp;
		int k = 1;
		while(rk[sa[n - 1]] != n - 1) {
			tmp.clear();
			for(int i = 0; i < k; i++) tmp.push_back(n - i - 1);
			for(auto i : sa) if(i >= k) tmp.push_back(i - k);
			
			fill(cnt.begin(), cnt.end(), 0);
			for(int i = 0; i < n; i++) cnt[rk[i]]++;
			for(int i = 1; i < n; i++) cnt[i] += cnt[i - 1];
			for(int i = n - 1; i >= 0; i--) sa[--cnt[rk[tmp[i]]]] = tmp[i];
			
			swap(tmp, rk);
			rk[sa[0]] = 0;
			for(int i = 1; i < n; i++) {
				rk[sa[i]] = rk[sa[i - 1]] + (tmp[sa[i - 1]] != tmp[sa[i]] 
					|| sa[i - 1] + k == n || tmp[sa[i - 1] + k] != tmp[sa[i] + k]
				);
			}
			k *= 2;
		}
		for(int i = 0, k = 0; i < n; i++) {
			if(rk[i] == 0) continue;
			if(k) k--;
			int j = sa[rk[i] - 1];
			while(j + k < n && i + k < n && s[i + k] == s[j + k]) k++;
			st[0][rk[i]] = k;
		}
		for(int j = 1; j < 20; j++) {
			for(int i = 0; i < n; i++) {
				if(i + (1 << j - 1) >= n) break;
				st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);
			}
		}
	} 
	int lcp(int x, int y) {
		assert(x != y);
		x = rk[x], y = rk[y];
		if(x > y) swap(x, y);
		x++;
		int j = __lg(y - x + 1);
		return min(st[j][x], st[j][y - (1 << j) + 1]);
	}
}; 

// 回文自动机
struct PAM {
	struct nd{
		int ch[26], len, num, fail;
	};
	int n, cnt, cur, ans;
	vector<nd> t;
	string s;
	
	int getFail(int u, int i) {
		while(i - t[u].len - 1 < 0 || s[i - t[u].len - 1] != s[i]) u = t[u].fail;
		return u;
	}
	PAM (string tt) {
		s = tt;
		n = s.size();
		t.resize(n + 10);
		cur = 0, cnt = 1;
		t[0].fail = 1, t[1].len = -1;
		for(int i = 0; i < n; i++) {
			if(i) s[i] = (s[i] - 97 + ans) % 26 + 97;
			int fa = getFail(cur, i);
			if(!t[fa].ch[s[i] - 'a']) {
				t[++cnt].fail = t[getFail(t[fa].fail, i)].ch[s[i] - 'a'];
				t[fa].ch[s[i] - 'a'] = cnt;
				t[cnt].len = t[fa].len + 2, t[cnt].num = t[t[cnt].fail].num + 1;
			}
			cur = t[fa].ch[s[i] - 'a'];
			ans = t[cur].num;
			cout << ans << ' ';
		}	
	}
};